using BepuUtilities.Memory;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Runtime.CompilerServices;
using System.Text;

namespace BepuUtilities.Collections
{
    public static class InsertionSort
    {
        // TODO：如果JIT曾经设法以最佳方式处理ISPAN索引器,我们可以使用更自然的基于ISPAN的实现。

        // [MethodImpl(MethodImplOptions.AggressiveInlining)]
        // 公共静电无效排序<Tkey,TValue,TKeySpan,TValueSpan,TCompeller>
        // (引用TKeySpan键,引用TValueSpan值,int start,int include siveEnd,引用TCompeller比较器)
        // 其中,TCompeller：IComperRef<TKey>
        // 其中TKeySpan：isspan<TKey>
        // 其中TValueSpan：isspan<TValue>
        // {
        // Debug.Assert(keys.Length<=values.Length);
        // Debug.Assert(start>=0&&start<keys.Length);
        // Debug.Assert(include siveEnd<keys.Length);//我们不检查include siveEnd是否>=start;零长度区域会被循环条件捕获。

        // for(int i=开始+1;i<=包含结束;++i)
        // {
        // var OriginalKey=keys[i];
        // var OriginalValue=值[i];
        // int compareIndex;
        // for(compareIndex=i-1;compareIndex>=开始;--compareIndex)
        // {
        // IF(comper.Compare(ref OriginalKey,ref key[compareIndex]))<0)
        // {
        // //将元素上移一个槽。
        // var upperSlotIndex=compareIndex+1;
        // keys[upperSlotIndex]=keys[compareIndex];
        // VALUES[upperSlotIndex]=VALUES[compareIndex];
        // }
        // 其他
        // 断线;
        // }
        // var targetIndex=compareIndex+1;
        // IF(targetIndex！=i)
        // {
        // //将原始索引下移。
        // KEYS[targetIndex]=OriginalKey;
        // 值[targetIndex]=OriginalValue;
        // }
        // }
        // }

        // TODO：通过对数据源进行抽象,可以有效地消除各种冗余实现。
        // 一种实现可以覆盖仅键、键+值和键-但仅内存-移动值。

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void Sort<TKey, TValue, TComparer>
           (ref TKey keys, ref TValue values, int start, int inclusiveEnd, ref TComparer comparer)
          where TComparer : IComparerRef<TKey>
        {
            for (int i = start + 1; i <= inclusiveEnd; ++i)
            {
                var originalKey = Unsafe.Add(ref keys, i);
                var originalValue = Unsafe.Add(ref values, i);
                int compareIndex;
                for (compareIndex = i - 1; compareIndex >= start; --compareIndex)
                {
                    if (comparer.Compare(ref originalKey, ref Unsafe.Add(ref keys, compareIndex)) < 0)
                    {
                        // 将元素上移一个插槽。
                        var upperSlotIndex = compareIndex + 1;
                        Unsafe.Add(ref keys, upperSlotIndex) = Unsafe.Add(ref keys, compareIndex);
                        Unsafe.Add(ref values, upperSlotIndex) = Unsafe.Add(ref values, compareIndex);
                    }
                    else
                        break;
                }
                var targetIndex = compareIndex + 1;
                if (targetIndex != i)
                {
                    // 将原始索引下移。
                    Unsafe.Add(ref keys, targetIndex) = originalKey;
                    Unsafe.Add(ref values, targetIndex) = originalValue;
                }
            }
        }



        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static void Sort<TKey, TComparer>
           (ref TKey keys, int start, int inclusiveEnd, ref TComparer comparer)
            where TComparer : IComparerRef<TKey>
        {
            for (int i = start + 1; i <= inclusiveEnd; ++i)
            {
                var originalKey = Unsafe.Add(ref keys, i);
                int compareIndex;
                for (compareIndex = i - 1; compareIndex >= start; --compareIndex)
                {
                    if (comparer.Compare(ref originalKey, ref Unsafe.Add(ref keys, compareIndex)) < 0)
                    {
                        // 将元素上移一个插槽。
                        var upperSlotIndex = compareIndex + 1;
                        Unsafe.Add(ref keys, upperSlotIndex) = Unsafe.Add(ref keys, compareIndex);
                    }
                    else
                        break;
                }
                var targetIndex = compareIndex + 1;
                if (targetIndex != i)
                {
                    // 将原始索引下移。
                    Unsafe.Add(ref keys, targetIndex) = originalKey;
                }
            }
        }
    }
}
